package 蓝桥杯算法;

public class day24 {
    public static void main(String[] args) {
        day24 a=new day24();
        int[] num={1,5,11,5};
        System.out.println(a.isvliad(num));
        int[] arr={2,7,4,1,8,1};
        System.out.println(a.stone(arr));

    }
    public boolean isvliad(int[] num){
        if(num.length==0||num==null){
            return false;
        }
        int n=num.length;
        int sum=0;
        for(int a:num){
            sum+=a;
        }
        if(sum%2!=0){
            return false;
        }
        int target=sum/2;
        int[] dp=new int[target+1];

        for(int i=0;i<n;i++){
            for(int j=target;j>=num[i];j--){
                dp[j]=Math.max(dp[j],dp[j-num[i]]+num[i]);
            }
        }
        return dp[target]==target;
    }
    public int stone(int[] num){
        if(num==null||num.length==0){
            return 0;
        }
        int sum=0;
        for(int i:num){
            sum+=i;
        }
        int n=sum>>1;//向下取整
        int[] dp=new int[n+1];
        dp[0]=0;
        for(int i=0;i<num.length;i++ ){
            for(int j=n;j>=num[i];j--){
                dp[j]=Math.max(dp[j],dp[j-num[i]]+num[i]);
            }
        }
        //求出最接近中间值的包，然后减去相关的值，求取其中的差值
        return sum-2*dp[n];
    }
    public int findTarget(int[] num,int target){
        int sum=0;
        for(int i:num){
            sum+=i;
        }
        if(Math.abs(target)>sum){
            return 0;
        }
        if((sum+target)%2==1){//无法得出结果
            return 0;
        }
        int bagsize=(target+sum)/2;
        int[] dp=new int[bagsize+1];
        for(int i=0;i<num.length;i++){
            for(int j=bagsize;j>=num[i];j--){
                dp[j]+=dp[j-num[i]];
            }
        }
        return dp[bagsize];
    }
}
